package data_structures_and_algorithms.tree.traverse.classic;

import common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName InTraverse
 * @Description: 中序遍历：左 -> 根 -> 右
 * @Author: yongliang.ma
 * @Create_time:2022/10/16 15:53
 */
public class InTraverse {


    List<Integer> list = new LinkedList<>();
    public List<Integer> inTraverse(TreeNode root){
        return list;
    }

    public void inTraverseCur(TreeNode treeNode){
        if (treeNode == null)
            return;
        inTraverseCur(treeNode.left);

        System.out.println(treeNode.val);

        inTraverseCur(treeNode.right);
    }
    public void inTraverseLoop(TreeNode treeNode){
        if (treeNode == null)
            return;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = treeNode;
        while (node != null || !stack.isEmpty()){
            while (node != null){
                stack.addFirst(node);
                node = node.left;
            }
            node = stack.removeFirst();
            list.add(node.val);
            node = node.right;
        }
    }

    // 非常容易理解
    public class ZuoGodVersion{
        /**
         * 处理步骤：
         *
         * 1、遍历的节点的左边界依次压栈
         *
         * 2、如果左边界为null，弹出节点即打印，然后赋值node以刚刚弹出的节点
         */
        public void inTraverseLoop(TreeNode root){
            if (root == null)
                return;
            Deque<TreeNode> deque = new LinkedList<>();
            TreeNode node = root;
            while (!deque.isEmpty() || node != null){
                if (node != null){
                    deque.push(node);
                    node = node.left;
                }else {
                    node = deque.pop();
                    list.add(node.val);
                    node = node.right;
                }
            }
        }
    }


}
